package com.ljc;

import com.ljc.dto.TreeNode;

/**
 * @author clj
 * @date 2022/12/5
 * @desc
 * Given a binary tree, find its minimum depth.
 *
 * The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
 *
 * Note: A leaf is a node with no children.
 *
 * Example 1:
 * Input: root = [3,9,20,null,null,15,7]
 * Output: 2
 *
 *  Example 2:
 * Input: root = [2,null,3,null,4,null,5,null,6]
 * Output: 5
 */
public class E111MinimumDepthOfBinaryTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);
//        root.left.right = new TreeNode(5);

        root.left.left.left = new TreeNode(11);

        root.right.left = new TreeNode(6);
//        root.right.right = new TreeNode(7);

        root.right.left.right = new TreeNode(13);

        root.right.left.right.left = new TreeNode(15);
        root.right.left.right.left.right = new TreeNode(16);
        root.right.left.right.left.right.left = new TreeNode(17);

        System.out.println(minDepth(root));
    }

    public static int minDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int m1 = minDepth(root.left);
        int m2 = minDepth(root.right);
        //1.如果左孩子和右孩子有为空的情况，直接返回m1+m2+1
        //2.如果都不为空，返回较小深度+1
        return root.left == null || root.right == null ? m1 + m2 + 1 : Math.min(m1,m2) + 1;
    }

}
